package com.demo.图;

import cn.hutool.core.lang.Console;
import com.demo.图.model.Edge;
import com.demo.图.model.Graph;
import com.demo.图.model.Vertex;
import org.junit.Test;

import java.io.Serializable;
import java.util.*;

/**
 * @author cl
 */
public class GraphTest {

    @Test
    public void 图的转换() {
        Console.log("图 邻接表 转 自定义类型:");
        Map<Integer, List<Integer>> adj = new HashMap<>(5);
        adj.put(2, Arrays.asList(8, 5));
        adj.put(5, Collections.singletonList(8));
        adj.put(8, Collections.singletonList(12));
        adj.put(7, Arrays.asList(2, 8));
        adj.put(12, Collections.emptyList());
        GraphConvert.adjacencyListConvertToGraph(adj).print();
    }

    @Test
    public void 无向图的宽度遍历() {
        Graph<Integer> graph = get1();
        Console.log("无向图 宽度遍历结果: {}", Arrays.toString(GraphTraverse.traverseByWidth(graph).stream().map(Vertex::getData).toArray()));
    }

    @Test
    public void 有向图的宽度遍历() {
        Graph<Integer> graph = get0();
        Console.log("有向图 宽度遍历结果: {}", Arrays.toString(GraphTraverse.traverseByWidth(graph).stream().map(Vertex::getData).toArray()));
    }

    @Test
    public void 无向图的深度遍历() {
        Graph<Integer> graph = get1();
        Console.log("无向图 深度遍历结果: {}", Arrays.toString(GraphTraverse.traverseByHeight(graph).stream().map(Vertex::getData).toArray()));
    }

    @Test
    public void 有向图的深度遍历() {
        Graph<Integer> graph = get0();
        Console.log("有向图 深度遍历结果: {}", Arrays.toString(GraphTraverse.traverseByHeight(graph).stream().map(Vertex::getData).toArray()));
    }

    @Test
    public void 无环拓扑排序() {
        Graph<Integer> graph = get0();
        Console.log("拓扑排序结果: {}, 是否有环: {}", Arrays.toString(GraphTopology.topologySort(graph).stream().map(Vertex::getData).toArray()), graph.vertexMap.size() > 0);
    }

    @Test
    public void 有环拓扑排序() {
        Graph<Integer> graph = get2();
        Console.log("拓扑排序结果: {}, 是否有环: {}", Arrays.toString(GraphTopology.topologySort(graph).stream().map(Vertex::getData).toArray()), graph.vertexMap.size() > 0);
    }

    public Graph<Integer> get0() {
        Console.log("有向图 邻接表 转 自定义类型:");
        Map<Integer, List<Integer>> adj = new HashMap<>(7);
        adj.put(1, Arrays.asList(3, 4));
        adj.put(2, Arrays.asList(3, 5));
        adj.put(3, Collections.singletonList(6));
        adj.put(4, Collections.singletonList(7));
        adj.put(5, Arrays.asList(4, 7));
        adj.put(6, Collections.singletonList(7));
        adj.put(7, Collections.emptyList());
        Graph<Integer> graph = GraphConvert.adjacencyListConvertToGraph(adj);
        graph.print();
        return graph;
    }

    public Graph<Integer> get1() {
        Console.log("无向图 邻接表 转 自定义类型:");
        Map<Integer, List<Integer>> adj = new HashMap<>(7);
        adj.put(1, Arrays.asList(3, 4));
        adj.put(2, Arrays.asList(3, 5));
        adj.put(3, Arrays.asList(1, 2, 6));
        adj.put(4, Arrays.asList(1, 5, 7));
        adj.put(5, Arrays.asList(2, 4, 7));
        adj.put(6, Arrays.asList(3, 7));
        adj.put(7, Arrays.asList(4, 5, 6));
        Graph<Integer> graph = GraphConvert.adjacencyListConvertToGraph(adj);
        graph.print();
        return graph;
    }

    public Graph<Integer> get2() {
        Console.log("有向图 有环 邻接表 转 自定义类型:");
        Map<Integer, List<Integer>> adj = new HashMap<>(7);
        adj.put(1, Arrays.asList(3, 4));
        adj.put(2, Arrays.asList(3, 5));
        adj.put(3, Collections.singletonList(6));
        adj.put(4, Collections.singletonList(7));
        adj.put(5, Collections.singletonList(4));
        adj.put(6, Collections.singletonList(7));
        adj.put(7, Collections.singletonList(5));
        Graph<Integer> graph = GraphConvert.adjacencyListConvertToGraph(adj);
        graph.print();
        return graph;
    }

    @Test
    public void kruskalTest() {
        Graph<Serializable> graph = get3();
        Console.log("图最小生成树 kruskal 算法执行");
        Graph<Serializable> result = GraphMST.Kruskal(graph);
        for (Edge<Serializable> edge : result.edges) {
            Console.log("边: {} -> {} {}", edge.from.data, edge.to.data, edge.weight);
        }
    }

    @Test
    public void primTest() {
        Graph<Serializable> graph = get3();
        Console.log("图最小生成树 kruskal 算法执行");
        Graph<Serializable> result = GraphMST.prim(graph);
        for (Edge<Serializable> edge : result.edges) {
            Console.log("边: {} -> {} {}", edge.from.data, edge.to.data, edge.weight);
        }
    }

    public Graph<Serializable> get3() {
        Console.log("无向图 有权:");
        Map<Serializable, List<List<Serializable>>> adj = new HashMap<>(7);
        adj.put("a", Arrays.asList(Arrays.asList("b", 18), Arrays.asList("g", 18), Arrays.asList("f", 19)));
        adj.put("b", Arrays.asList(Arrays.asList("a", 18), Arrays.asList("g", 20), Arrays.asList("c", 8)));
        adj.put("c", Arrays.asList(Arrays.asList("b", 8), Arrays.asList("d", 20)));
        adj.put("d", Arrays.asList(Arrays.asList("c", 20), Arrays.asList("g", 15), Arrays.asList("f", 16), Arrays.asList("e", 9)));
        adj.put("e", Arrays.asList(Arrays.asList("d", 9), Arrays.asList("f", 3)));
        adj.put("f", Arrays.asList(Arrays.asList("a", 19), Arrays.asList("g", 15), Arrays.asList("d", 16), Arrays.asList("e", 3)));
        adj.put("g", Arrays.asList(Arrays.asList("a", 18), Arrays.asList("b", 20), Arrays.asList("d", 15),  Arrays.asList("f", 15)));
        Graph<Serializable> graph = GraphConvert.adjacencyListConvertToGraphWithWeight(adj);
        graph.print();
        return graph;
    }

    public Graph<Integer> get4() {
        Console.log("无向图 有权:");
        Map<Integer, List<List<Integer>>> adj = new HashMap<>(7);
        adj.put(1, Arrays.asList(Arrays.asList(2, 12), Arrays.asList(6, 16), Arrays.asList(7, 14)));
        adj.put(2, Arrays.asList(Arrays.asList(1, 12), Arrays.asList(3, 10), Arrays.asList(6, 7)));
        adj.put(3, Arrays.asList(Arrays.asList(2, 10), Arrays.asList(4, 3), Arrays.asList(5, 5), Arrays.asList(6, 6)));
        adj.put(4, Arrays.asList(Arrays.asList(3, 3), Arrays.asList(5, 4)));
        adj.put(5, Arrays.asList(Arrays.asList(3, 5), Arrays.asList(4, 4), Arrays.asList(6, 2), Arrays.asList(7, 8)));
        adj.put(6, Arrays.asList(Arrays.asList(1, 16), Arrays.asList(2, 7), Arrays.asList(3, 6), Arrays.asList(5, 2), Arrays.asList(7, 9)));
        adj.put(7, Arrays.asList(Arrays.asList(1, 14), Arrays.asList(5, 8), Arrays.asList(6, 9)));
        Graph<Integer> graph = GraphConvert.adjacencyListConvertToGraphWithWeight(adj);
        graph.print();
        return graph;
    }

    @Test
    public void 迪克斯拉算法() {
        Graph<Integer> graph = get4();
        Vertex<Integer> start = graph.getVertexMap().get(1);
        Map<Vertex<Integer>, Integer> result = GraphDijkstra.dijkstra(graph, start);
        for (Map.Entry<Vertex<Integer>, Integer> entry : result.entrySet()) {
            Console.log("{} 到 {} 的最短距离为: {}", start.data, entry.getKey().data, entry.getValue());
        }
    }
}
